<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1658：[Usaco2006 Mar]Water Slides 滑水</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2006 Mar]Water Slides 滑水</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2006 Mar]Water Slides 滑水</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2006 Mar]Water Slides 滑水                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium; ">It's a hot summer day, and Farmer John is letting Betsy go to the water park where she intends to ride every single slide. The water park has N (1 &lt;= N &lt;= 10,000) platforms (numbered 1..N) from which to enter the M (1 &lt;= M &lt;= 10,000) water slides. Each water slide starts at the top of some platform and ends at the bottom of some platform (possibly the same one). Some platforms might have more than one slide; some might not have any.  The park is very thin, so the platforms lie along a straight line, each platform at a position Xi (0 &lt;= Xi &lt;= 100,000) meters from one end of the park. One walks from one platform to the next via a sidewalk parallel to the line of platforms.The platforms of the water park are weakly connected; that is, the park cannot be divided into two sets of platforms with no slides running between the two sets. Both the entrance and exit to the park are at platform 1, so Betsy will start and end there.  In order to spend more time on the slides, Betsy wants to walk as little as possible. Find the minimum distance Betsy must travel along the ground in order to try every slide in the park exactly once without repeating.</span></p>
<p></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">炎热的夏日里，约翰带贝茜去水上乐园滑水．滑水是在一条笔直的人工河里进行的，沿河设有</span><span lang="EN-US">N(1</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">N</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">10000)</span><span style="font-family: 宋体; ">个中转站，并开通了</span><span lang="EN-US">M(1</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">M</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">10000)</span><span style="font-family: 宋体; ">条滑水路线．路线的起点和终点总在某个中转站上，起点和终点可能相同．有些中转站可能是许多条路线的起点或终点，而有些站则可能没有在任何路线里被用上．贝茜希望能把所有的路线都滑一遍．</span><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">所有中转站排成一条直线，每个中转站位于离河的源头</span><span lang="EN-US">Xi(0</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">Xi</span><span style="font-family: 宋体; ">&le;</span><span lang="EN-US">100000)</span><span style="font-family: 宋体; ">米处．沿着河边的人行道，贝茜可以从任意位置走到任意一个中转站．</span><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">中转站与滑水路线的布局满足下述的性质：任意两个中转站之间都有滑水路线直接成间接相连．水上乐园的入口与出口都在</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">号中转站旁，也就是说，贝茜的滑水路线的起点和终点都是</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">号中转站．</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">为了更好地享受滑水的快乐，贝茜希望自己花在走路上的时间越少越好．请你帮她计算一</span></span><span style="font-family: 宋体; font-size: medium; ">下，如果按她的计划，把所有的路线都不重复地滑一遍，那她至少要走多少路．</span></p>
<p class="MsoNormal"></p></p><hr/><h3>输入格式</h3><p><p>* Line 1: Two integers, N and M.</p>
<p>* Lines 2..N+1: Line i+1 contains one integer, Xi, the position of         platform i.  * Lines N+2..M+N+1: Line i+N+1 contains two integers, Si and Di,         respectively the start and end platforms of a slide.</p>
<p><span lang="EN-US" style="font-size: medium; ">&nbsp; &nbsp;&nbsp;</span><span style="font-size: medium; font-family: 宋体; ">第</span><span lang="EN-US" style="font-size: medium; ">1</span><span style="font-size: medium; font-family: 宋体; ">行：两个整数</span><span lang="EN-US" style="font-size: medium; ">N</span><span style="font-size: medium; font-family: 宋体; ">和</span><span lang="EN-US" style="font-size: medium; ">M</span><span style="font-size: medium; font-family: 宋体; ">，用空格隔开．</span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">到</span><span lang="EN-US">N+1</span><span style="font-family: 宋体; ">行：第</span><span lang="EN-US">i+l</span><span style="font-family: 宋体; ">行包括一个整数</span><span lang="EN-US">Xi</span><span style="font-family: 宋体; ">，表示</span><span lang="EN-US">i</span><span style="font-family: 宋体; ">号中转站距河源头的距离．</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">第</span><span lang="EN-US">N+2</span><span style="font-family: 宋体; ">到</span><span lang="EN-US">M+N+1</span><span style="font-family: 宋体; ">行：第</span><span lang="EN-US">i+N+1</span><span style="font-family: 宋体; ">行包括两个整数</span><span lang="EN-US">Si</span><span style="font-family: 宋体; ">和</span><span lang="EN-US">Di</span><span style="font-family: 宋体; ">，分别表示了一条滑水路线的起</span></span><span style="font-family: 宋体; font-size: medium; ">点和终点．</span></p>
<p class="MsoNormal"></p></p><hr/><h3>输出格式</h3><p><p><span style="font-size: medium; ">* Line 1: One integer, the minimum number of meters Betsy must walk.</span></p>
<p><span style="font-size: medium; "><span lang="EN-US" style="font-family: 'Times New Roman'; ">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">输出一个整数，即贝茜要走的路程长度至少为多少米</span></span></p></p><hr/><h3>样例输入</h3><pre>5 7
5
3
1
7
10
1 2
1 2
2 3
3 1
4 5
1 5
4 1
</pre><hr/><h3>样例输出</h3><pre>8
</pre><hr/><h3>提示</h3><p><p><span style="font-size: medium; ">&nbsp;<span lang="EN-US">&nbsp;&nbsp;</span><span style="font-family: 宋体; ">贝茜先按</span><span lang="EN-US">1~2~3~1~2</span><span style="font-family: 宋体; ">路径滑水．然后走</span></span><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="2" unitname="米" w:st="on"><span style="font-size: medium; "><span lang="EN-US">2</span><span style="font-family: 宋体; ">米</span></span></st1:chmetcnv><span style="font-size: medium; "><span style="font-family: 宋体; ">，回到</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">．她再滑行到</span><span lang="EN-US">5</span><span style="font-family: 宋体; ">，走到</span><span lang="EN-US">4</span><span style="font-family: 宋体; ">，滑行</span>  </span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span style="font-family: 宋体; ">到</span><span lang="EN-US">5</span><span style="font-family: 宋体; ">，走到</span><span lang="EN-US">4</span><span style="font-family: 宋体; ">，最后滑回</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">（数字代表中转站号）．</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">这样，她所走的总路程为</span></span><st1:chmetcnv tcsc="0" numbertype="1" negative="False" hasspace="False" sourcevalue="8" unitname="米" w:st="on"><span style="font-size: medium; "><span lang="EN-US">8</span><span style="font-family: 宋体; ">米</span></span></st1:chmetcnv><span style="font-size: medium; "><span style="font-family: 宋体; ">．</span></span></p></p><hr/><h3>题目来源</h3><p>没有写明来源</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1658" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1658" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>